Maps

Without Maps: Linear Lookup Time

When we have a list of objects and need to search for an item in that list, the time required to search will grow linearly with the number of objects. The more items added to the list, the longer it will take to iterate over all of the items. Processing a list of items like this is said to take linear time, because a graph of the relationship looks like a straight line:

With Maps: Constant Lookup Time

Maps provide a solution. Maps are data structures that use key-value pairs. That is, every value in the map is paired with a key. When we want to retrieve a value, we simply provide the corresponding key.

Importantly, this retrieval is performed in constant time, meaning that the amount of time required to retrieve an item from the map takes a certain, fixed (constant) amount of time, and this time doesn't change based on how many items we add.

Map is an Interface

The Java Map is an Interface that provides three different distinct views of the data:

• A list of the keys
• A list of the values
• A set of key-value mappings

We'll see how to use these in the upcoming exercise.

Map Syntax

Let's go over the basic syntax for creating and using maps.

Creating a Map Object

In the Collections framework, the Map is an interface and cannot be directly used to insatiate a class. In the example below, we are creating a Map of people. Notice that we are using the concrete class HashMap to instantiate our Map object.

Map<String, Person> mapOfPeople = new HashMap<String, Person>();

Adding to a Map

Next we will look at adding objects to our Map. Remember that a Map takes a key-value pair. So when we add an object we will be adding the key and the value. In the example below we are using the email as the key and the value will be our Person object. To add to the Map we use the put method.

Person mike = new Person("Mike", "mike@email.com");
Person shaun = new Person("Shaun", "shaun@email.com");
Person sally = new Person("Sally", "sally@email.com");
Person cesar = new Person("Cesar", "cesar@email.com");

mapOfPeople.put(mike.getEmail(), mike);
mapOfPeople.put(shaun.getEmail(), shaun);
mapOfPeople.put(sally.getEmail(), sally);
mapOfPeople.put(cesar.getEmail(), cesar);

Retrieving an object from a Map

In this example, we will be looking at the syntax to retrieve a Person object from the Map using an email as the key.

mapOfPeople.get("mike@email.com");

Iterating over a Map

In our final example, let's see how we can iterate over our Map using a for-each loop. Remember that each Map has three distinct views for seeing the data. We can get the keys, the values, or key-value mapping. In the example below we are displaying all of the keys for our Map.

for (String email : mapOfPeople.keySet()) {
    System.out.println(email);
}